The process of checking an arrangement of shapes to determine if it satisfies one or more boundary distance (BD) constraints between those shapes has many valuable commercial applications. For brevity we will refer to this process as boundary distance constraint verification (BDCV). Applications of BDCV include, for example, their use in methods to search for arrangements of shapes that exactly or approximately satisfy one or more BD constraints and, their use in checking the results of methods that attempt to generate arrangements of shapes that exactly or approximately satisfy one or more BD constraints to verify that the BD constraints have been exactly or approximately satisfied.
Instances of the BDCV problem include, for example, verifying that two or three dimensional components on or in a manufactured product do not overlap and all components are contained within the product's boundaries. Examples include verifying the BD constraints between: the components inside the body of a car; the components inside the case of a printer; the rooms in a building; the components on a circuit board or; the components on VLSI chip. Other instances include verifying that an arrangement of one or more products or product components in or on a piece of material from which they are to be extracted have sufficient space between them to allow for the kerf of the cutting tool. Examples include versifying the BD constraints between the components of a pair of pants on a bolt of fabric or the components of a ship on a sheet of steel. Other instances in the area of packing and shipping include verifying that an arrangement of packages inside a shipping container satisfy the requirement that no packages occupy the same space and all packages fit inside the container. Some of these instances can further be extended into 4-dimensional problems where, for example, time constraints, or time dependant motion requirements are present.